#define _CRT_SECURE_NO_WARNINGS

#include <stdlib.h>

///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode ListNode;
//
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    if (head == NULL)
//    {
//        return NULL;
//    }
//    ListNode* newhead = head;
//    for (; newhead;)
//    {
//        if (newhead->val == val)
//        {
//            newhead = newhead->next;
//        }
//        else
//        {
//            break;
//        }
//    }
//    if (newhead == NULL)
//    {
//        return NULL;
//    }
//    ListNode* current = newhead;
//    ListNode* prev = NULL;
//    for (; current;)
//    {
//        if (current->val == val)
//        {
//            prev->next = current->next;
//            current = current->next;
//        }
//        else
//        {
//            prev = current;
//            current = current->next;
//        }
//    }
//
//    return newhead;
//}

//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (!head)
//    {
//        return NULL;
//    }
//    ListNode* p = NULL;
//    ListNode* c = head;
//    ListNode* n = c->next;
//    for (; c;)
//    {
//        c->next = p;
//        p = c;
//        c = n;
//        if (n)
//        {
//            n = n->next;
//        }
//    }
//
//    return p;
//}


//typedef struct ListNode ListNode;
//struct ListNode* middleNode(struct ListNode* head)
//{
//    int length = 0;
//    ListNode* current = head;
//    for (; current;)
//    {
//        length++;
//        current = current->next;
//    }
//    length = length / 2;
//    current = head;
//    for (int i = 0; i < length; i++)
//    {
//        current = current->next;
//    }
//
//    return current;
//}
//typedef struct ListNode ListNode;
//int compare(const void* a, const void* b)
//{
//    int x = *(int*)a;
//    int y = *(int*)b;
//
//    return x - y;
//}
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    int len1 = 0, len2 = 0;
//    ListNode* current = list1;
//    for (; current;)
//    {
//        current = current->next;
//        len1++;
//    }
//    current = list2;
//    for (; current;)
//    {
//        current = current->next;
//        len2++;
//    }
//    int* arr = malloc((len1 + len2) * sizeof(int));
//    int i = 0, flag = 0;
//    current = list1;
//    for (; i < len1 + len2;)
//    {
//        if (current)
//        {
//            arr[i] = current->val;
//            current = current->next;
//            i++;
//        }
//        else if (!flag)
//        {
//            current = list2;
//            flag++;
//        }
//        else
//        {
//            break;
//        }
//    }
//    qsort(arr, len1 + len2, sizeof(int), compare);
//    ListNode* ret = NULL;
//    current = NULL;
//    ListNode* temp = NULL;
//    for (i = 0; i < len1 + len2; i++)
//    {
//        current = malloc(sizeof(ListNode));
//        if (i)
//        {
//            temp->next = current;
//        }
//        else
//        {
//            ret = current;
//        }
//        current->val = arr[i];
//        temp = current;
//    }
//    if (current)
//    {
//        current->next = NULL;
//    }
//
//    return ret;
//}


//typedef struct ListNode ListNode;
//struct ListNode* middleNode(struct ListNode* head)
//{
//    ListNode* fast = head;
//    ListNode* slow = head;
//
//    for (; fast && fast->next;)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//
//    return slow;
//} 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//class PalindromeList
//{
//public:
//    bool chkPalindrome(ListNode* A)
//    {
//        int i = 0;
//        int arr[900] = { 0 };
//        ListNode* current = A;
//        for (i = 0; current; i++)
//        {
//            arr[i] = current->val;
//            current = current->next;
//        }
//        i--;
//        int j = 0;
//
//        for (; j < i; j++, i--)
//        {
//            if (arr[i] != arr[j])
//            {
//                return false;
//            }
//        }
//
//        return true;
//    }
//};